How do we mathematically describe the invisible threads connecting society? Whether it is the Bacon Numbers linking Bela Lugosi to Hollywood icons or Similarity Graphs clustering data points based on proximity, Graph Theory provides the formal language $G = (V, E)$ to model these discrete universes.
1. The Anatomy of Graphs
At its core, a graph consists of a set of vertices ($V$) and a set of edges ($E$). However, the rules of engagement vary based on the structure:
- Simple Graph: The most elegant form; it prohibits loops (edges connecting a vertex to itself) and parallel edges (redundant edges between the same two points).
- Multigraph: Permits loops and parallel edges, often used to model multiple types of interactions (e.g., text vs. call) between the same two nodes.
- Isolated Vertex: A vertex $v$ is isolated if no edge is incident on it, representing an object with no relationships in the current set.
In data science, we often use a Dissimilarity Function to construct graphs:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
We draw an edge between $v$ and $w$ only if $s(v, w)$ falls below a specific threshold, effectively building a network of "neighbors."
2. Paths, Connectivity, and Components
A path is a sequence of vertices and edges. If a path visits no vertex more than once, it is a simple path. Connectivity is the heartbeat of the graph:
- Connected Graph: A path exists between every pair of vertices in the graph.
- Components: If a graph is not connected, it breaks into disjoint pieces called components. Each component is a maximal connected subgraph.
3. Subgraphs: The Architecture of Subsets
A subgraph $G' = (V', E')$ is a subset of a graph $G$ such that every vertex in $V'$ exists in $V$, and every edge in $E'$ connects vertices found in $V'$. Identifying subgraphs is critical for detecting local patterns within global networks.